package com.leetcode.no28;

public class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() == 0) {
            return -1;
        }

        int m = haystack.length();
        int n = needle.length();


        for (int i = 0; i <= m - n; i++) {
            if (haystack.substring(i, i + n).equals(needle)) {
                return i;
            }
        }
        return -1;
    }


}

class Solution01 {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() == 0) {
            return -1;
        }

        int m = haystack.length();
        int n = needle.length();
        int pm = 0;

        while (pm <= m - n) {

            // find the position of the first needle character
            // in the haystack string
            // 找到首部匹配
            while (pm <= m - n && haystack.charAt(pm) != needle.charAt(0)) {
                pm ++;
            }

            // compute the max match string
            int currLen = 0, pn = 0;
            while(pn < n && pm < m && haystack.charAt(pm) == needle.charAt(pn)){
                ++pm;
                ++pn;
                ++currLen;
            }

            if(currLen == n){
                return  pm - currLen;
            }

            pm = pm - currLen + 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        String a = "qwertyuiopasdfgh";
        String b = "fg";

        Solution01 test = new Solution01();
        System.out.print(test.strStr(a, b));
    }


}